package com.leetcode;

/*
    *********************************************
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
           佛祖保佑       永无BUG
 */

import java.util.ArrayList;
import java.util.List;

/**
 * @author wry
 * @description:
 * @date 9/24/25 PM4:33
 */
public class No449 {

    public String serialize(TreeNode root) {
        if (root == null) {
            return null;
        }
        List<Integer> list = doSerialize(root);
        return list.toString();
    }

    public List<Integer> doSerialize(TreeNode root) {
        if (root == null) {
            return null;
        }
        List<Integer> list = new ArrayList<>();
        list.add(root.val);
        if (root.left != null) {
            list.addAll(doSerialize(root.left));
        }
        if (root.right != null) {
            list.addAll(doSerialize(root.right));
        }
        return list;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null) {
            return null;
        }
        String[] split = data.split(",");
        List<Integer> list = new ArrayList<>();
        for (String s : split) {
            list.add(Integer.valueOf(s));
        }
        return doDeserialize(list);
    }

    public TreeNode doDeserialize(List<Integer> data) {
        if (data == null || data.isEmpty()) {
            return null;
        }
        TreeNode node = new TreeNode(data.getFirst());
        if (data.size() == 1) {
            return node;
        }
        int index = 0;
        for (int i = 1; i < data.size(); i++) {
            if (data.get(i) < node.val) {
                index = i;
            } else {
                break;
            }
        }
        if (index > 0) {
            node.left = doDeserialize(data.subList(1, index + 1));
        }
        if (index < data.size() - 1) {
            node.right = doDeserialize(data.subList(index + 1, data.size()));
        }
        return node;
    }
}
